package com.smday.linkedlist;

/**
 * @author Summerday
 */
public class Josephu {

    public static void main(String[] args) {
        CircleSingleLinkedList cll = new CircleSingleLinkedList();

        cll.create(5);

        cll.showBoy();

        cll.countBoy(1,2,5);
    }
}
//创建环形的单向链表

class CircleSingleLinkedList {
    //创建一个first节点
    private Boy first;

    public void create(int nums) {
        //nums 校验,最少要两个
        if (nums <= 1) {
            System.out.println("数据不正确");
            return;
        }
        //辅助指针
        Boy curBoy = null;
        Boy boy;
        //for循环创建hx链表
        for (int i = 1; i <= nums; i++) {
            boy = new Boy(i);
            //如果是第一个
            if (i == 1) {
                first = boy;
                first.setNext(first);
                //让curBoy指向第一个
                curBoy = first;
            } else {
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }

        }
    }

    //遍历
    public void showBoy() {
        //判断链表是否为空
        if (first == null) {
            System.out.println("链表为空!");
            return;
        }

        //first不能动,需要使用辅助指针完成遍历
        Boy curBoy = first;
        //遍历
/*        while (curBoy.getNext() != first) {

            System.out.printf("小孩的编号为 : %d \n", curBoy.getNo());

            curBoy = curBoy.getNext();
        }
        System.out.printf("小孩的编号为 : %d \n", curBoy.getNo());*/

        do {
            System.out.printf("小孩的编号为 : %d \n", curBoy.getNo());
            curBoy = curBoy.getNext();
            //先执行do里面的语句, 已经getNext.
        } while (curBoy != first);

    }

    /**
     * 根据用户的输入,计算出出圈的顺序
     * @param startNo 从第几个开始数
     * @param countNum 数几下
     * @param nums 表示最初有多少个小孩在圈中
     */
    public void countBoy(int startNo, int countNum,int nums){

        //数据校验
        if(first == null||startNo<1||startNo>nums){
            System.out.println("参数有误");
            return;
        }

        //创建辅助指针,帮助完成小孩出圈
        Boy helper = first;

        //让helper事先指向最后一个节点
        while(helper.getNext()!=first){
            helper = helper.getNext();
        }
        //报数前,线移动k-1次
        for(int j = 0;j<startNo-1;j++){
            first = first.getNext();
            helper = helper.getNext();
        }

        //当小孩报数时,让first helper指针同时移动m-1次

        while(helper!=first){
            //让first helper指针同时移动countNum-1次
            for(int j = 0;j<countNum-1;j++){
                first = first.getNext();
                helper = helper.getNext();
            }
            //此时first指向的节点解释要出圈的节点
            System.out.printf("小孩%d出圈\n",first.getNo());
            //这时将first指向的小孩节点出圈
            first = first.getNext();
            helper.setNext(first);
        }
        //此时只有一个人 helper == first
        System.out.printf("最后留在圈中的编号%d",helper.getNo());


    }
}


//创建Boy类,表示一个节点
class Boy {

    private int no;
    private Boy next;

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}
